#include "List/linkList.h"

linkList::linkList()
{
    head = new Node;       
    head->data = 0;        // 将头结点的数据域定义为0     
    head->next = NULL;     // 头结点的下一个定义为NULL
}

linkList::~linkList()
{
    delete head;           // 删除头结点
}

void linkList::createLinkList(int n)
{
    Node *pnew, *ptemp;
    ptemp = head;
    if (n < 0)            // 当输入的值有误时，处理异常
    {
        cout << "node number is error." << endl;
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < n; i++)  //将值一个一个插入单链表中
    {
        pnew = new Node;
        cout << "please input No." << i + 1 << "value.";
        cin >> pnew->data;      
        pnew->next = nullptr;      // 新节点的下一个地址为NULLWW
        ptemp->next = pnew;     // 当前结点的下一个地址设为新节点
        ptemp = pnew;           // 将当前结点设为新节点
    }  
}

void linkList::travalLinkList()
{
    if (head == NULL || head->next == NULL)
    {
        cout << "Error:the linklist is null." << endl;
    }
    Node *p = head;             // 令指针指向头节点
    while(p->next != NULL)      // 当指针的下一个地址不为空时，循环输出p的数据域
    {
        p = p->next;            // p指向p的下一个地址
        cout << p->data << "" ;
    }  
}

int linkList::getLength()
{
    int count = 0;          //定义count计数
    Node *p = head->next;   //定义p指向头结点
    while (p != NULL)       //当指针的下一个地址不为空时，count+1
    {
        count++;            
        p = p->next;        //p指向p的下一个地址
    }
    return count;           //返回count的数据
}   

bool linkList::IsEmpty()
{
    if(head->next == nullptr)
    {
        return true;
    }

    return false;
}

Node * linkList::findNode(int data)
{
    Node * p = head;
    if(p == NULL)
    {
        cout << "the link list is NUll." << endl;
        return ERROE;           //当为空表时，报异常
    }
    else
    {
        while (p->next != NULL) //循环每一个节点
        {
            if(p->data == data)
            {
                return p;       //返回指针域
            }
            p = p->next;        
        }

        if(p->data == data)     //当前节点判断
        {
            return p;
        }

        return NULL;            //未查询到结果
        
    }
}

void linkList::insertElemAtEnd(int data)
{
    Node * pnew = new Node;     //定义一个Node结点指针pnew
    pnew->next = NULL;          //定义pnew的数据域和指针域
    pnew->data = data;
    Node * p = head;            //定义指针p指向头结点
    if(head == NULL)
    {
        head = pnew;
    }
    else
    {
        while (p->next != NULL) //循环知道最后一个节点，将pnew放置在最后
        {
            p = p->next;
        }
        p->next = pnew;
    }
}

void linkList::insertElemAtIndex(int data, int n)
{
    if(n < 1 || n>getLength())
    {
        cout << "The Input Value is invalid." << endl;  //输入有误报异常
    }
    else
    {
        Node * ptemp = new Node;        //创建一个新的节点
        ptemp->data = data;             //定义数据域 
        Node * p = head;                //创建一个指针指向头结点
        int i = 1;
        while (n > i)                   //遍历到指定的位置
        {
            p = p->next;
            i++;
        }
        // 插入的节点指针域指向当前p指向的,p的指针域指向插入的结点。
        ptemp->next = p->next;           //将新节点插入到指定位置
        p->next = ptemp;
        
    }
}

void linkList::insertElemAtHead(int data)
{
    Node * pnew = new Node;         //创建一个新的节点
    pnew->data = data;              //定义数据域 
    Node * p = head;                //创建一个指针指向头结点
    if(head == NULL)
    {
        head = pnew;
    }
    pnew->next = p->next;           //将新节点插入到指定位置
    p->next = pnew;
}

void linkList::deleteElemAtEnd()
{
    Node * p = head;                //创建一个指针指向头结点
    Node * ptemp = NULL;            //创建一个占位节点
    if(p->next == NULL)             //判断链表是否为空
    {
        cout << "The linkList is NUlL." << endl;
    }
    else
    {
        while (p->next != NULL)     //循环到尾部的前一个
        {
            ptemp = p;              //将ptemp指向尾部的前一个节点
            p = p->next;            //p指向最后一个节点
        }
        delete p;                   //删除尾部节点
        p = NULL;
        ptemp->next = NULL;
    }
}

void linkList::deleteAll()
{
    Node * p = head->next;
    Node * ptemp = new Node;
    while (p != NULL)               //在头结点的下一个节点逐个删除节点
    {
        ptemp = p;
        p = p->next;
        head->next = p;
        ptemp->next = NULL;
        delete ptemp;
    }
    head->next = NULL;              //头结点的下一个节点指向NULL
}

void linkList::deleteElemAtPoint(int data)
{
    Node * ptemp = findNode(data);
    if(ptemp == head->next)
    {
        deleteElemAtHead();
    }
    else
    {
        Node * p = head;
        while (p->next != ptemp)
        {
            p = p->next;
        }
        p->next = ptemp->next;
        delete ptemp;
        ptemp = NULL;
    }
}

void linkList::deleteElemAtHead()
{
    Node * p = head;
    if (p == NULL || p->next == NULL)           //判断是否为空表，报异常
    {
        cout << "The linkList is null Link." << endl;
    }
    else
    {
        Node * ptemp = NULL;                    //创建一个占位节点
        p = p->next;
        ptemp = p->next;                        //将头结点的下下个节点指向占位节点
        delete p;                               //删除头结点的下一个节点
        p = NULL;
        head->next = ptemp;                     //头结点的指针更换
    }  
}

Node *linkList::iteration_reverse(Node *head)
{
    if(head == nullptr || head->next == nullptr)
    {
        return head;
    }
    else {
        Node * beg = nullptr;
        Node * mid = head;
        Node * end = head->next;
        //一直遍历
        while(1)
        {
            //修改 mid 所指节点的指向
            mid->next = beg;
            //此时判断 end 是否为 NULL，如果成立则退出循环
            if(end == nullptr)
            {
                break;
            }
            //整体向后移动 3 个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        //最后修改 head 头指针的指向
        head = mid;
        return head;
    }
}

Node *linkList::recursive_reverse(Node *head)
{
    //递归的出口
    if(head == nullptr || head->next == nullptr)  // 空链或只有一个结点，直接返回头指针
    {
        return head;
    }
    else {
        //一直递归，找到链表中最后一个节点
        Node * new_head = recursive_reverse(head->next);
        //当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
        //递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。

        //每退出一层，都需要改变 head->next 节点指针域的指向，同时令 head 所指节点的指针域为 NULL。
        head->next->next = head;
        head->next = nullptr;
        //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
        return new_head;
    }
}


void testRunLinkList()
{
    linkList *l;
    l = new linkList;
    int i;
    cout << "1.创建单链表   2.遍历单链表   3.获取单链表的长度   4.判断单链表是否为空   5.获取节点\n";
    cout << "6.在尾部插入指定元素   7.在指定位置插入指定元素   8.在头部插入指定元素\n";
    cout << "9.在尾部删除元素   10.删除所有元素   11.删除指定元素   12.在头部删除元素   0.退出" << endl;
    do
    {
        cout << "请输入要执行的操作: ";
        cin >> i;
        switch (i)
        {
        case 1:
            int n;
            cout << "请输入单链表的长度: ";
            cin >> n;
            l->createLinkList(n);
            break;
        case 2:
            l->travalLinkList();
            break;
        case 3:
            cout << "该单链表的长度为" << l->getLength() << endl;
            break;
        case 4:
            if (l->IsEmpty() == 1)
                cout << "该单链表是空表" << endl;
            else
            {
                cout << "该单链表不是空表" << endl;
            }
            break;
        case 5:
            int data;
            cout << "请输入要获取节点的值: ";
            cin >> data;
            cout << "该节点的值为" << l->findNode(data)->data << endl;
			break;
		case 6:
			int endData;
			cout << "请输入要在尾部插入的值: ";
			cin >> endData;
			l->insertElemAtEnd(endData);
			break;
		case 7:
			int pointData;
			int index;
			cout << "请输入要插入的数据: ";
			cin >> pointData;
			cout << "请输入要插入数据的位置: ";
			cin >> index;
			l->insertElemAtIndex(pointData, index);
			break;
		case 8:
			int headData;
			cout << "请输入要在头部插入的值: ";
			cin >> headData;
			l->insertElemAtHead(headData);
			break;
		case 9:
			l->deleteElemAtEnd();
			break;
		case 10:
			l->deleteAll();
			break;
		case 11:
			int pointDeleteData;
			cout << "请输入要删除的数据: ";
			cin >> pointDeleteData;
			l->deleteElemAtPoint(pointDeleteData);
			break;
		case 12:
			l->deleteElemAtHead();
			break;
		default:
			break;
		}
	}while (i != 0);
    delete l;
	system("pause");
}

/*
 * 链表类应该包含基本的增、改、删、查等操作，由于其各种功能的实现是很相似的，所以下面给出了需要实现的典型函数：
构造函数：
isEmpty()判断是否为空；
size()返回链表长度；
insert()头插、尾插、中间插入节点；
delete()删除节点；
getNode()获取节点；
traversal()遍历链表；
*/

/* 初始化时需要创建头节点，作为头指针 */
doubleLinkedList::doubleLinkedList() {
    // create head node
    head = new doubleNode;
    head->pre = nullptr;
    head->next = nullptr;
    head->setData(666);
}

/*在插入和删除等操作中，需要频繁的进行节点获取操作。所以应该封装为单独的函数用于节点获取 */
doubleNode *doubleLinkedList::getNode(int index){
    doubleNode * current = head;
    int currentCount = 0;
    // end of loop condition
    while(currentCount <= index)
    {
        current = current->next;
        currentCount++;
    }

    return current;
}

/*  获取链表长度时需要判断链表是否为空，从而确定是否采用遍历的方式计算链表的长度。
 *  由于采用的不是循环链表，所以循环的结束条件是判断是否指向空节点*/
int doubleLinkedList::size(){
    if(isEmpty())
    {
        return 0;
    }
    else {
        int count = 0;
        doubleNode * current = head->next;
        // end of loop condition
        while(current == nullptr)
        {
            current = current->next;
            count++;
        }
        return count;
    }
}

/* 插入节点依旧包含头插法，尾插法和任意位置的插入。
 * 插入操作与单向链表的最大区别在于节点的指针移动较为复杂，需要将插入位置前后两个节点与新节点均建立联系 */
void doubleLinkedList::insert(int data, int index){
    doubleNode * node = new doubleNode;
    node->setData(data);
    if(isEmpty())
    {
        head->next = node;
        node->pre = head;
        return;
    }
    // head insert
    if(index == 0)
    {
        node->next = head->next;
        head->next->pre = node;
        node->pre = head;
        head->next = node;
    }
    // tail insert
    else if(index >= this->size() - 1)
    {
        doubleNode * ptemp = this->getNode(this->size() - 1);
        ptemp->next = node;
        node->pre = ptemp;
    }
    // everywhere
    else {
        doubleNode * pre = this->getNode(index);
        doubleNode * next = pre->next;
        node->next = pre->next;
        node->pre = pre;
        pre->next = node;
        node->next->pre = node;
    }
}

/* 从双向链表的任一个节点开始遍历整个链表，但是下面的实现依旧是从头结点开始的，循环的结束依旧是指向空指针 */
void doubleLinkedList::traversal(){
    if(!isEmpty())
    {
        doubleNode * current = head;
        while (current) {
            cout << current->getData() << endl;
            current = current->next;

        }
    }
}

/* 已经定义了用于获取节点的getNode()函数，所以remove()函数只需要进行指针移动操作。
 * 将所要删除的节点的直接前驱节点和直接后继节点相连 */
void doubleLinkedList::remove(int index){
    if((index <= (this->size()-1)) && (index > 0))
    {
        doubleNode * node = this->getNode(index);
        doubleNode * pre = node->pre;
        doubleNode * next = node->next;
        pre->next = next;
        next->pre = pre;
    }
}

/* 对于双向链表来说，判断是否为空只需要判断头指针是否指向其他Node节点 */
bool doubleLinkedList::isEmpty(){
    if(head->next == nullptr)
    {
        return true;
    }
    else {
        return false;
    }
}

cycleLinkedList::cycleLinkedList(){
    head->next = nullptr;
    head->data = 666;
}

void cycleLinkedList::insert(Node *node)
{
    int data;
    cout << "请输入要插入的元素：" ;
    cin >> data;
    Node * ptemp = new Node;
    ptemp->data = data;
    //初始化一个新的结点，准备进行链接
    if(head != nullptr)
    {
        Node * p = head;
        while(p->next != head)
        {
            p = p->next;
        }
        p->next = node;
        node->next = head;
    }
    else {
        cout << "头结点已无元素" << endl;
    }
}
